package NewCoder;

import java.util.LinkedList;

public class BM11 {
    //反转链表来相加
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1==null) return head2;
        if(head2==null) return head1;
        head1=reverse(head1);
        head2=reverse(head2);
        int carry=0;
        ListNode dum=new ListNode(-1);
        ListNode res=dum;
        while(head1!=null || head2!=null || carry!=0){
            int val1=head1==null?0:head1.val;
            int val2=head2==null?0:head2.val;
            int tmp=val1+val2+carry;
            carry=tmp/10;
            tmp%=10;
            res.next=new ListNode(tmp);
            res=res.next;
            if(head1!=null){
                head1=head1.next;
            }
            if(head2!=null){
                head2=head2.next;
            }
        }
        return reverse(dum.next);
    }
    public ListNode reverse(ListNode node){
        if(node==null) return null;
        ListNode cur=node;
        ListNode pre=null;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }

    //使用栈来进行加减法和进位操作
//    public ListNode addInList (ListNode head1, ListNode head2) {
//        // write code here
//        LinkedList<Integer> list1=new LinkedList<>();
//        LinkedList<Integer> list2=new LinkedList<>();
//        put(list1,head1);
//        put(list2,head2);
//        ListNode newNode=null;
//        ListNode head=null;
//        int carry=0;
//        while(!list1.isEmpty() || !list2.isEmpty() || carry!=0){
//            int x=(list1.isEmpty())?0:list1.pop();
//            int y=(list2.isEmpty())?0:list2.pop();
//            int temp=x+y+carry;
//            carry=temp/10;
//            newNode=new ListNode(temp%10);
//            newNode.next=head;
//            head=newNode;
//        }
//        return head;
//    }
//    private void put( LinkedList<Integer> s1,ListNode head){
//        if(s1==null) s1=new LinkedList<>();
//        while(head!=null){
//            s1.push(head.val);
//            head=head.next;
//        }
//    }
}
